|
In computational complexity theory, a planted clique or hidden clique in an undirected graph is a clique formed from another graph by selecting a subset of vertices and adding edges between each pair of vertices in the subset. The planted clique problem is the algorithmic problem of distinguishing random graphs from graphs that have a planted clique. This is a variation of the clique problem; it may be solved in quasi-polynomial time but is conjectured not to be solvable in polynomial time for intermediate values of the clique size. The conjecture that no polynomial time solution exists is called the planted clique conjecture; it has been used as a computational hardness assumption. ==Definition== A clique in a graph is a subset of vertices, all of which are adjacent to each other. A planted clique is a clique created from another graph by adding edges between all pairs of a selected subset of vertices. The planted clique problem can be formalized as a decision problem over a random distribution on graphs, parameterized by two numbers, (the number of vertices), and (the size of the clique). These parameters may be used to generate a graph, by the following random process:〔.〕 #Create an Erdős–Rényi random graph on vertices by choosing independently for each pair of vertices whether to include an edge connecting that pair, with probability 1/2 for each pair. #Decide whether or not to add a clique to the graph, with probability 1/2; if not, return the graph formed in step 1. #Choose randomly a subset of of the vertices and add an edge (if one is not already present) between each pair of the selected vertices. The problem is then to determine algorithmically whether one of the graphs resulting from this process contains a clique of at least vertices. With high probability, the size of the largest clique in an -vertex random graph is close to . And when is larger than the square root of , the vertices of a planted clique can be recognized as having unusually large degrees, making a planted clique easy to find. Therefore, the most interesting range of values for the parameter is between these two values,〔 : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Planted clique」の詳細全文を読む スポンサード リンク
|